データ構造のナビゲーションのための方法、システム、およびコンピュータ・プログラム（データ構造のナビゲーションのための方法およびシステム）

专利摘要:
データ構造のナビゲーションのための方法およびシステムを提供する。 この方法は、ランタイム時にデータ構造（１０１）内で１つまたは複数の要素（１１０）を見つけるために、データ構造（１０１）の照会のための入力パス式（１０４）を受信することを含む。入力パス式（１０４）は１つまたは複数のパス・ステップを含む。この方法は、データ構造（１０１）のスキーマ（１０３）にアクセスすること、および、１つまたは複数の要素（１１０）に関する情報を取得することを含む。パス式（１０４）は、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数のパス・ステップにおけるインデックスを指定するように修正される。一実施形態では、さらにパス式（１０４）は、任意のワイルドカード文字を拡張して、要素（１１０）の１つまたは複数の全パスを指定し、２つまたはそれ以上の全パスが存在する場合、それらは合併演算子によって組み合わせられ、修正されたパス式は、ランタイム時にデータ構造（１０１）を照会（１１１）するために使用される。
公开号:JP2011510372A
申请号:JP2010541777
申请日:2009-01-07
公开日:2011-03-31
发明作者:コールマン、アンドリュー、ジョン
申请人:インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｓｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ；
IPC主号:G06F17-30

专利说明:

[0001] 本発明は、データ構造のナビゲーションの分野に関する。具体的に言えば、データ構造を照会するためにパス式（path expression）を使用するナビゲーションに関する。]
背景技術

[0002] データ構造は、パス式を使用して照会することができる。たとえばＸＰａｔｈ（ＸＭＬ Ｐａｔｈ Ｌａｎｇｕａｇｅ）の何らかの変形などのパス言語を使用した、ＸＭＬ（拡張マークアップ言語）データの格納および照会が可能な、多くのデータベース・システムが存在する。ＸＰａｔｈは、ツリー・データ構造を照会するＷ３Ｃ標準方法である。ＸＰａｔｈは、パス式に基づいてＸＭＬデータを照会可能にするものである。本明細書はＸＰａｔｈ式および照会について言及するが、他のパス言語で作成された他の形のパス式を含むものと解釈されるべきである。パス式とは、ＸＭＬドキュメントの階層構造へのパスを指定する任意の式のことである。パス式によって識別されるＸＭＬドキュメントの一部は、パス式に一致する任意のパスの終わりにあるＸＭＬドキュメントの構造内に常駐する部分である。]
[0003] ＸＭＬドキュメントは、しばしば、ドキュメント・オブジェクト・モデル（ＤＯＭ）構造またはツリーとして表される。パス照会は、これらの構造をトラバースすることによって評価されるため、照会最適化の要件は、トラバースされるノードの数を効率的に減らすことである。]
[0004] ＸＭＬスキーマは、ＸＭＬドキュメントの精密な構造形式を定義する。このスキーマはランタイム時に使用できない可能性がある。]
[0005] ドキュメントのスキーマにアクセスできないパス・ランタイム・エンジンを考えてみると、解釈済みのＤＯＭツリーのみを照会している。ユーザが自由形式パス式を入力する（すなわちパス・ビルダを介さない）オーサリング・ツールは、スキーマにアクセスできない。]
先行技術

[0006] カリフォルニア大学デービス校、コンピュータ・サイエンス学部、April KwongおよびMichael Gertzによる「Schema-basedOptimization of XPath Expression」]
発明が解決しようとする課題

[0007] ユーザが、ＸＭＬドキュメント内の任意の要素を、そこまでの全パスを指定する必要なく、名前で見つけられるようにするために、下位（descendant）（／／）パスを使用することが有益であろう。しかしながら、下位軸は、この要素のすべての出現を見つけるためにＤＯＭツリー全体をトラバースする必要があるため、ランタイム・エンジンにとって非常に効率が悪い。]
課題を解決するための手段

[0008] カリフォルニア大学デービス校、コンピュータ・サイエンス学部、April KwongおよびMichaelGertzによる「Schema-based Optimization of XPathExpression」では、スキーマから生成されたパス等価クラスを使用するＸＰａｔｈ式の最適化を開示している。この最適化方法は、ＸＰａｔｈ式におけるワイルドカードの拡張を含む。]
[0009] 本発明の第１の態様によれば、ランタイム時にデータ構造内で１つまたは複数の要素を見つけるために、データ構造の照会のための入力パス式を受信することであって、入力パス式は１つまたは複数のパス・ステップを含む、受信すること、データ構造のスキーマにアクセスし、１つまたは複数の要素に関する情報を取得すること、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数のパス・ステップにおけるインデックスを指定するようにパス式を修正すること、および、ランタイム時にデータ構造を照会するために修正されたパス式を使用することを含む、データ構造のナビゲーションのための方法が提供される。]
[0010] 本発明の第２の態様によれば、ランタイム時にデータ構造内で１つまたは複数の要素を見つけるために、データ構造の照会のための入力パス式を受信するための手段であって、入力パス式は１つまたは複数のパス・ステップを含む、受信するための手段と、データ構造のスキーマにアクセスし、１つまたは複数の要素に関する情報を取得するための手段と、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数のパス・ステップにおけるインデックスを指定するようにパス式を修正するための手段と、データ構造を照会するためにランタイム時に使用するように修正されたパス式を出力するための手段とを備える、データ構造のナビゲーションのためのシステムが提供される。]
[0011] 本発明の第３の態様によれば、ランタイム時にデータ構造内で１つまたは複数の要素を見つけるために、データ構造の照会のための入力パス式を受信するステップであって、入力パス式は１つまたは複数のパス・ステップを含む、受信するステップと、データ構造のスキーマにアクセスし、１つまたは複数の要素に関する情報を取得するステップと、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数のパス・ステップにおけるインデックスを指定するようにパス式を修正するステップと、ランタイム時にデータ構造を照会するために修正されたパス式を使用するステップとを実行するための、コンピュータ読み取り可能プログラム・コード手段を備える、コンピュータ読み取り可能ストレージ・メディア上に格納されたコンピュータ・プログラム製品が提供される。]
[0012] 好ましくは、費用のかかるメモリ・データ構造の基本テーブルおよび構造体の完全スキャンを招くことなく、ＸＭＬドキュメントからデータを取り出すための、パス・ベースの照会に関する方法を提供することによって、パス・ベースの照会の処理時間を改善するソリューションが提供される。好ましくは、照会における要素の反復に関する情報を取得および使用するソリューションが提供される。]
[0013] 記載された方法およびシステムは、データ構造内の要素が反復可能であり、反復が存在するかどうか、および反復がどれだけあるかを知ることによって、データ構造のナビゲーションを最適化することが可能である、基礎となるモデルを有するデータ構造の照会を実行可能にするものである。]
[0014] 本発明は、好ましくはオリジナルのパス式を採用し、スキーマを使用して、これをランタイム・エンジンによってより効率的に処理可能な形に変換する。スキーマは、任意の要素をドキュメント・ルートまで遡って追跡するために必要な情報を含むため、要素への全パスを生成することができる。これによって好ましくは、ランタイム・エンジンが、要素を「検索する」のではなく、直接それへとナビゲートすることが可能になる。]
[0015] 次に、本発明の諸実施形態について、添付の図面を参照しながら単なる例として説明する。]
図面の簡単な説明

[0016] 本発明の一実施形態に従ったシステムを示す概略図である。
本発明の一実施形態に従ったシステムを示す概略図である。
本発明の一実施形態を内部に実装可能なコンピュータ・システムを示すブロック図である。
本発明の一実施形態に従ったドキュメント構造を示す概略図である。
本発明の一実施形態に従った汎用プロセスを示す流れ図である。
本発明の一実施形態に従ったプロセス例を示す流れ図である。]
実施例

[0017] 図１を参照すると、データ構造１０１内の１つまたは複数の要素１１０を見つけるために、ランタイム・エンジン１０２によってデータ構造１０１が照会される、システム１００の概略図が示されている。] 図１
[0018] データ構造１０１は、たとえば、ドキュメント・オブジェクト・モデル（ＤＯＭ）ツリーとして表されるＸＭＬドキュメントとすることができる。他の例では、データ構造１０１は、同様のツリー・データ構造に解析される非ＸＭＬデータである。一実施形態では、データ構造１０１はメッセージ・ブローカによって照会されるメッセージである。データ構造１０１は、関連付けられたスキーマ１０３を有する。]
[0019] パス式１０４は、１つまたは複数の要素１１０を見つけるためにパス式１０４の出現に関してデータ構造１０１を検索するランタイム・エンジン１０２へ、照会１１１として入力される。]
[0020] ツールキット１０５は、ランタイム・エンジン１０２へと配置される照会１１１を構築するために使用される。記載されたシステム１００では、ツールキット１０５はパス式１０４を修正するためにスキーマ１０３にアクセスする。]
[0021] 照会されているデータ構造１０１のスキーマ１０３からの情報を使用して、パス式１０４は、照会されている要素１１０への全パスおよび他の情報を含むように修正される。これは、要素１１０に関する検索よりもむしろ要素１１０の追跡に役立ち、ランタイム・エンジン１０２の効率を上げる。またスキーマ１０３が、照会されている要素１１０の出現数を示す場合、ランタイム・エンジン１０２は、その特定の要素１１０の一定の出現数が見つけられた後、停止することができる。]
[0022] 図２を参照すると、パス式１０４が入力されたツールキット１０５の詳細図が示されている。スキーマは、スキーマ情報１２０を取得するために参照される。修正子１２１は、照会出力１２２を提供するために、スキーマ情報１２０を使用してパス式１０４を修正する。照会出力１２２は、データ構造を照会するためにランタイム・エンジンによって使用される。たとえばスキーマを使用して、照会されている要素の出現数を決定することが可能であり、次にこの情報は、照会出力１２２に述語（predicate）を追加するために、修正子１２１によって使用される。] 図２
[0023] 図３を参照すると、ツールキット１０５を実装するための例示的システムは、バス・システム２０３を介してメモリ要素に直接または間接的に結合された少なくとも１つのプロセッサ２０１を含む、プログラム・コードの格納あるいは実行またはその両方に好適な、処理システム２００を含む。メモリ要素は、プログラム・コードの実際の実行中に使用されるローカル・メモリ、大容量ストレージ、および、実行中にコードを大容量ストレージから取り出さなければならない回数を減らすために少なくともいくつかのプログラム・コードの一時ストレージを提供するキャッシュ・メモリを、含むことができる。] 図３
[0024] メモリ要素は、読み取り専用メモリ（ＲＯＭ）２０４およびランダム・アクセス・メモリ（ＲＡＭ）２０５の形の、システム・メモリ２０２を含むことができる。基本入力／出力システム（ＢＩＯＳ）２０６は、ＲＯＭ２０４に格納可能である。システム・ソフトウェア２０７は、オペレーティング・システム・ソフトウェア２０８を含み、ＲＡＭ２０５内に格納可能である。ソフトウェア・アプリケーション２１０もＲＡＭ２０５内に格納可能である。]
[0025] システム２００は、磁気ハード・ディスク・ドライブなどの１次ストレージ手段２１１、ならびに、磁気ディスク・ドライブおよび光ディスク・ドライブなどの２次ストレージ手段２１２も、含むことができる。ドライブおよびそれらの関連付けられたコンピュータ読み取り可能メディアは、コンピュータ実行可能命令、データ構造、プログラム・モジュール、およびシステム２００に関する他のデータの、不揮発性ストレージを提供する。ソフトウェア・アプリケーションは、１次および２次のストレージ手段２１１、２１２、ならびにシステム・メモリ２０２上に格納可能である。]
[0026] コンピューティング・システム２００は、ネットワーク・アダプタ２１６を介した１つまたは複数のリモート・コンピュータへの論理接続を使用する、ネットワーク化環境内で動作可能である。]
[0027] 入力／出力デバイス２１３は、直接、または介在するＩ／Ｏコントローラを介して、システムに結合することができる。ユーザは、キーボード、ポインティング・デバイス、または他の入力デバイス（たとえば、マイクロフォン、ジョイ・スティック、ゲーム・パッド、衛星用アンテナ、スキャナなど）などの入力デバイスを介して、コマンドおよび情報をシステム２００に入力することができる。出力デバイスは、スピーカ、プリンタなどを含むことができる。ディスプレイ・デバイス２１４も、ビデオ・アダプタ２１５などのインターフェースを介してシステム・バス２０３に接続される。]
[0028] パス言語は、データ構造（ＸＭＬドキュメントなど）のツリー表現に基づくものであり、ツリー周辺をナビゲートし、様々な基準によってノードを選択する機能を提供する。パス式は、１つのノード、現在の「コンテキスト・ノード」から、他のノードまたはノード・セットへと取得するための、一連のステップとして作成される。このステップは、「／」（すなわちパス）文字によって分離される。各ステップは、軸指定子、ノード・テスト、および述語という、３つのコンポーネントを有する。]
[0029] 最も単純なパスは、




の形を取り、これは、データ構造の最も外側の要素を形成するＡ要素の子であるＢ要素の子であるＣ要素を選択する。]
[0030] より複雑な式は、デフォルトの「子」軸以外の軸、単純名以外のノード・テスト、または述語を指定することによって、構築可能であり、これは任意のステップ後に角括弧で作成することができる。たとえば、式




は、それ自体が子、または他の、現在のコンテキスト・ノードの子であるＡ要素のより深い下位（「／／」）である、Ｂ要素の子（「／」）である、第１の要素（「［１］」）を、その名前（「＊」）であれば何でも、選択する（この式は「／」で始まっていない）。ドキュメント内にいくつかの好適なＢ要素が存在する場合、これは実際には、それらのすべての第１の子のセットを戻す。軸指定子は、データ構造のツリー表現内のナビゲーション方向を示す。]
[0031] いかなる複雑さの式も、述語として角括弧内に指定可能であり、これは、パス式によって先行ノードが一致することになる前に満たされなければならない。ステップ内の述語数には制限が無く、パス内の最終ステップに限定される必要がない。それらは任意の深さまでネストすることができる。述語内に指定されたパスは、現在のステップの（すなわち、直前のノード・テストの）コンテキストで開始され、そのコンテキストを変更しない。すべての述語は、一致の出現に関して満たされなければならない。述語の順序は有意であり、各述語はロケーション・ステップの選択されたノード・セットを順にフィルタリングする。]
[0032] ＸＭＬスキーマは、あるタイプのＸＭＬドキュメントの記述であり、通常は、ＸＭＬ自体によって課せられる基本構文制約に加えて、そのタイプのドキュメントの構造およびコンテンツへの制約に関して表される。ＸＭＬスキーマは、比較的高レベルの抽象でのドキュメント・タイプの観点を提供する。スキーマは、非ＸＭＬデータ構造に関連して使用することもできる。たとえば、ＸＭＬスキーマを使用してドキュメント構造をモデル化した後、ＸＳＤ（ＸＭＬスキーマ定義）注釈を使用することによって、各要素の物理フォーマットを記述する。]
[0033] ＸＭＬスキーマを表すために特別に開発された言語がある。ＸＭＬ仕様固有のドキュメント・タイプ定義（ＤＴＤ）言語は、比較的機能が制限されているが、スキーマの表現とは別にＸＭＬにおける他の用途も有する、スキーマ言語である。２つの他の非常に普及している、より表現的なＸＭＬスキーマ言語は、ＸＭＬスキーマ（Ｗ３Ｃ）およびＲＥＬＡＸ ＮＧ（ＲＥｇｕｌａｒ ＬＡｎｇｕａｇｅ ｆｏｒ ＸＭＬ Ｎｅｘｔ Ｇｅｎｅｒａｔｉｏｎ）である。ＸＭＬドキュメントをスキーマと関連付けるためのメカニズムは、スキーマ言語に応じて変化する。関連付けは、ＸＭＬドキュメント自体の中のマークアップを介して、または何らかの外部手段を介して、達成可能である。]
[0034] 説明されたシステムでは、パス式は以下のような３通りの可能な方法で修正できる。
１．ワイルドカード「＊」または下位軸「／／」の単純な拡張であり、スキーマは１つの可能な解決のみを示唆する。
２．パス合併演算子（unionoperator）「｜」と組み合わされた複数のパスを備える式への、ワイルドカード「＊」または下位軸「／／」の拡張であり、スキーマは複数の可能な解決を示唆する。
３．インデックス（［１］）の挿入であり、スキーマは要素が１回のみ現れることを示唆する。同様に、［ｐｏｓｉｔｉｏｎ（）＜＝ｎ］の挿入であり、スキーマは要素がｎ回出現可能であることを示唆し、ここでｎ＞１である。]
[0035] 例示のために、以下のＸＭＬドキュメントを使用して作業例を示す。]
[0036] このドキュメントは、以下のＸＭＬスキーマ（ＸＳＤ）によってモデル化することができる。]
[0037] スキーマは、各要素の最低および最高の出現を含む、ＸＭＬドキュメントの許容構造を記述する。スキーマは、図４に示されたドキュメント構造（スキーマ・ツリー）３００を表す。] 図４
[0038] 図４に示されたドキュメント構造３００は、「ｄｏｃｕｍｅｎｔ」のルート・ノード３１１からの２つの分岐３１０、３２０を含む。第１の分岐３１０は、子ノード３１４「ｉｔｅｍ」を有することが可能な子ノード３１３「ｌｉｓｔ」を備える、ルート・ノード３１１の子ノード３１２「ｔｏｐｉｃ」を含む。「ｉｔｅｍ」のノード３１４、３２３は、ゼロまたはそれ以上の出現を有することができる。他のノード３１１、３１２、３１３、３２２は１つの出現のみを含むことができる。] 図４
[0039] 次に図５を参照すると、流れ図４００は、データ構造をナビゲートするための汎用プロセスを示す。パス式は、データ構造内の１つまたは複数の要素を見つけるために入力される（４０１）。データ構造に関するスキーマにアクセスし（４０２）、パス式の要素に関する情報が取得される。要素に関する最大出現がスキーマから参照され（４０３）、出現を制限する必要があれば、述語がパス式に添付される。１つまたは複数の全パス式が取得され（４０４）、２つまたはそれ以上ある場合は組み合わされる。] 図５
[0040] パス式は、要素に関する取得された情報を参照しながら修正される。修正されたパス式は、データ構造内の１つまたは複数の要素を見つけるためにランタイム・エンジンへと出力される（４０５）。]
[0041] この作業例では、ＸＰａｔｈ式「／／ｉｔｅｍ」が与えられた場合、下位軸「／／」を拡張するため、および「最初の１つのみを選択する」述語「［１］」を追加するために、図６の流れ図に示されるような以下のステップが実施される。
１．初期の最適化された式「／ｉｔｅｍ」を作成するために、「／」文字のうちの１つを除去する（５０１）。
２．「ｉｔｅｍ」という名前の要素を検索する「深さ優先（depth first）」様式で、スキーマ・ツリーをトラバースする（５０２）。
３．要素が見つかったかどうかを判別し（５０３）、見つかった場合は続行し、見つからなかった場合、プロセスは終了する（５０４）。
４．見つかった要素が第１の要素であるかどうかを判別する（５０５）。第１の要素である場合は続行し、第１の要素でない場合は、合併演算子を使用して以前の式に添付する（５０６）。
５．「ｉｔｅｍ」要素が見つかった場合、スキーマ内の「ｍａｘＯｃｃｕｒｓ」属性に注目する（５０７）。この属性が「１」（この属性が存在しない場合のデフォルトである）であるかどうかを判別し（５０８）、「１」である場合は、要素名に述語「［１］」を添付する（５１０）。「１」より大きいかまたは「未制限」の場合、述語を添付しない（５０９）。
６．スキーマ・ツリー内の現在の要素の親に進む（５１１）。
７．親がルート・ノードであるかどうかを判別する（５１２）。ルート・ノードである場合、別の「ｉｔｅｍ」の検索に進む（５０２）。
８．親がルート・ノードでない場合、スキーマから名前を抽出し（５１３）、分離文字「／」によって分離された以前のステップの前にこれを挿入する。
９．ステップ５０７へと折り返して、必要に応じて要素名に述語を添付し、次の親に進む。「ルート」要素に達するまで続行する。
１０．他の「ｉｔｅｍ」要素が見つかった場合、ツリーのこの分岐について他の最適化されたパス式を作成する。これを、合併演算子「｜」によって分離された以前の式に添付する（５０６）。スキーム・ツリー内にそれ以上の「ｉｔｅｍ」の出現が見つからなくなるまで、トラバースを続行する。] 図６
[0042] 以下に、前述のステップに続くような、最適化された式の構築を示す（オリジナルの式「／／ｉｔｅｍ」は、各ステップでの変更が下線で示される）。]
[0043] さらに汎用ケースでは、一般的な原理は、ＸＰａｔｈ式を１回に１要素ステップずつ進み、ワイルドカード「＊」があれば要素名に置き換え、下位軸「／／」があれば完全修飾されたパスに置き換えることである。複数の要素がワイルドカードに一致する場合、それぞれが順番に考慮される。後続のステップでは、ある特定の一致が有効なパスへと至ることができず、そのような場合、その一致は廃棄される旨を示すことができる。複数の一致が可能な場合、各式は組み合わされ、ＸＰａｔｈ合併演算子「｜」によって分離される。]
[0044] 「＊／ｔｏｐｉｃ／／ｉｔｅｍ」の式について考えてみる。
１．「スキーマ・カーソル」をスキーマ・ツリーのルートに設定し、「ＸＰａｔｈカーソル」をオリジナルＸＰａｔｈ式の第１のステップに設定する。
２．スキーマ・ツリーを、スキーマ・カーソル位置から深さ優先でトラバースする。
３．スキーマ・ツリー内のカーソル要素がＸＰａｔｈステップに一致する（ワイルドカードがいずれかの要素に一致する）場合、
ａ．要素名（ワイルドカードの場合はスキーマ・ツリーから）を最適化されたＸＰａｔｈ式に添付する。
ｂ．スキーマ内の「ｍａｘＯｃｃｕｒｓ」属性に注目する。この属性が「１」（この属性が存在しない場合のデフォルトである）である場合、要素名に述語「［１］」を添付する。「１」より大きいかまたは「未制限」の場合、述語を添付しない。
ｃ．ＸＰａｔｈカーソルがオリジナルＸＰａｔｈ式内の最終ステップである場合、反復を停止し、このステージで構築された新しい式を部分リストに追加して、第２ステージからトラバースを続行する。
ｄ．ＸＰａｔｈカーソルを、オリジナルＸＰａｔｈ式内の次のステップに移動する。次のステップが下位軸「／／」によって分離されている場合、
ｉ．以前に記述されたアルゴリズムを使用して、これを拡張する（拡張アルゴリズム内の「ルート」要素を、ここでは「／／」の前の要素であるものと定義する）。
ｉｉ．拡張の結果、合併演算子「｜」によって分離された複数のパスが生じた場合、これまでに最適化された式を複製し、各部分の初めに添付する必要がある。各部分は、このアルゴリズムの剰余に対して別々に扱われなければならない。（たとえば、「／ｄｏｃｕｍｅｎｔ／／ｉｔｅｍ」は、拡張前に「／ｄｏｃｕｍｅｎｔ［１］／／ｉｔｅｍ」を生成することになる。このカーソル位置から「／／ｉｔｅｍ」を拡張すると、「／ｔｏｐｉｃ［１］／ｌｉｓｔ［１］／ｉｔｅｍ｜／ｉｎｄｅｘ［１］／ｉｔｅｍ」を生成することになる。このステップの後、２つの部分は、／ｄｏｃｕｍｅｎｔ［１］／ｔｏｐｉｃ［１］／ｌｉｓｔ［１］／ｉｔｅｍおよび／ｄｏｃｕｍｅｎｔ［１］／ｉｎｄｅｘ［１］／ｉｔｅｍとなり、各部分は別々に扱われるものとする。）
ｅ．スキーマ・カーソルのそれぞれの子について、次に、スキーマ・カーソルを子に設定する。ステージ３に再帰する。（このステージで、各子は最適化された式における別々の部分を表すことになり、そのほとんどが、おそらくはデッドエンドであり、破棄されることになる。アルゴリズムの終わりで、合併演算子［｜］を使用してすべての剰余部分が組み合せられる。）
一致しない場合、
ａ．アルゴリズムのステージ２以降に構築されたパスのこの部分を破棄する。スキーマ・カーソルおよびＸＰａｔｈカーソルを、以前ステージ２の際にそれらがいた場所に再設定する。ステージ２からトラバースを続行する。
４．合併演算子「｜」によって分離された部分リストを組み合わせて、最終式を生成する。]
[0045] 以下に、前述のステップに続くような、最適化された式の構築を示す（オリジナルの式「＊／ｔｏｐｉｃ／／ｉｔｅｍ」は、各ステップでの変更が下線で示される）。]
[0046] 「／／ｉｔｅｍ」などの式が入力された場合、このいずれかの出現を見つけるために、データ構造全体をトラバースしなければならない。しかしながらこれは、スキーマを参照することによって取得された全パス式「／ｄｏｃｕｍｅｎｔ／ｔｏｐｉｃ／ｌｉｓｔ／ｉｔｅｍ」を指定することによって、ランタイム・エンジンがｉｔｅｍを直接ナビゲートできるような形に変換することができる。]
[0047] スキーマが、ｉｔｅｍが反復しないように指定した場合、各パス・ステップ上に明示的ｉｎｄｅｘを配置し、第１の一致、たとえば「／ｄｏｃｕｍｅｎｔ［１］／ｔｏｐｉｃ［１］／ｌｉｓｔ［１］／ｉｔｅｍ」を見つけた場合、検索を停止できる旨を、ランタイム・エンジンに伝えることができる。「ｉｔｅｍ」は反復要素であるが、その上位（ancestor）要素は反復要素でないことに留意されたい。]
[0048] データ構造の異なる部分に名前付き要素「ｉｔｅｍ」が現われた場合、それらは合併演算子「｜」を使用して組み合わせることができる。たとえば、「／ｄｏｃｕｍｅｎｔ［１］／ｔｏｐｉｃ［１］／ｌｉｓｔ［１］／ｉｔｅｍ｜／ｄｏｃｕｍｅｎｔ［１］／ｉｎｄｅｘ［１］／ｉｔｅｍ」となる。この最後の式は、所与のスキーマに関するオリジナルの「／／ｉｔｅｍ」と等価であるが、そのスキーマにアクセスできないランタイム・エンジンによってより効率的に処理可能な形である。]
[0049] スキーマは、要素が所与の回数だけ、たとえば２回出現するように指定することが可能である。ＸＰａｔｈステップ「／ｅｌｅｍｅｎｔ［２］」は、第１の２つの要素ではなく第２の要素を戻すことになる。正しい結果を得るために、［ｐｏｓｉｔｉｏｎ（）＜＝２］を添付すべきである。従来のシステムでは、ユーザは、ツリーをナビゲートするためのランタイム・エンジンを望むことを示し、すべての一致要素を戻すために、「／ａａａ／ｂｂｂ」を指定する。しかしながら、時折、戻す要素が１つしかない場合があり、ＸＰａｔｈパーザ（parser）は、従来、完全なツリーを解析しなければならないため、多くの不必要な処理を実行しなければならない。ユーザは、たとえば第１番目などの、ある数の要素のみを希望する場合があり、これを示すため、照会内に、たとえば「ａａａ／ｂｂｂ［１］」などと断定することができる。以前には、パーザは依然として完全なリストに戻すが、その後、ユーザが必要とする数を戻すように、そのセットを絞り込むものであった。]
[0050] 説明されたシステムでは、ツールキットは、照会されている要素の出現数を決定するために使用される、データ構造スキーマにアクセスする。次に、この情報を使用して、各照会に述語が追加される。したがって、２つの「ａａａ／ｂｂｂ」要素のみが存在し、ユーザはこうした要素のすべてについて照会していることが判別された場合、最初の２つの要素のみを探した後、解析を停止すべきであることを、パーザに示すように、照会を修正することができる。]
[0051] 説明された方法およびシステムは、ＥＳＢ（Ｅｎｔｅｒｐｒｉｓｅ Ｓｅｒｖｉｃｅ Ｂｕｓ）、および、メッセージを照会するメッセージ・ブローカの形のランタイム・エンジンを含むＸＭＬ処理製品で、適用可能である。]
[0052] この方法は、照会として使用するように修正されたパス式を改善するために、ネットワークを介したクライアントへのサービスとして提供することも可能である。]
[0053] 本発明は、完全なハードウェア実施形態、完全なソフトウェア実施形態、または、ハードウェアおよびソフトウェアの両方の要素を含む実施形態の形を取ることができる。好ましい実施形態では、本発明は、ファームウェア、常駐ソフトウェア、マイクロコードなどを含むがこれらに限定されない、ソフトウェア内に実装される。]
[0054] 本発明は、コンピュータまたは任意の命令実行システムによって、あるいはそれらに関して使用するためのプログラム・コードを提供する、コンピュータ使用可能メディアまたはコンピュータ読み取り可能メディアからのアクセスが可能な、コンピュータ・プログラム製品の形を取ることができる。説明の目的で、コンピュータ使用可能メディアまたはコンピュータ読み取り可能メディアは、命令実行システム、装置、またはデバイスによって、あるいはそれらに関して使用するためのプログラムの含有、格納、通信、伝搬、または移送が可能な、任意の装置とすることができる。]
[0055] メディアは、電子、磁気、光、電磁、赤外線、または半導体のシステム（あるいは装置またはデバイス）、あるいは伝搬メディアとすることができる。コンピュータ読み取り可能メディアの例には、半導体またはソリッド・ステート・メモリ、磁気テープ、取り外し可能コンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛性磁気ディスク、および光ディスクが含まれる。光ディスクの現行例には、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク読み取り／書き込み（ＣＤ−Ｒ／Ｗ）、およびＤＶＤが含まれる。]
[0056] 本発明の範囲を逸脱することなく、前述の内容に対する改良および修正を実行することが可能である。]

权利要求:

請求項1
ランタイム時にデータ構造（１０１）内で１つまたは複数の要素（１１０）を見つけるために、データ構造（１０１）の照会のための入力パス式（１０４）を受信するステップであって、前記入力パス式（１０４）は１つまたは複数のパス・ステップを含む、受信するステップと、前記データ構造（１０１）のスキーマ（１０３）にアクセスするステップ、および、前記１つまたは複数の要素（１１０）に関する情報を取得するステップと、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数のパス・ステップにおけるインデックスを指定するように前記入力パス式（１０４）を修正するステップと、ランタイム時に前記データ構造（１０１）を照会（１１１）するために前記修正されたパス式を使用するステップと、を含む、データ構造（１０１）のナビゲーションのための方法。
請求項2
前記入力パス式（１０４）が、ワイルドカード文字または下位軸のうちの１つまたは複数を含む、請求項１に記載の方法。
請求項3
前記入力パス式（１０４）を修正するステップが前記要素（１１０）の１つまたは複数の全パスを指定し、２つまたはそれ以上の全パスが合併演算子によって組み合わせられる、請求項１または２に記載の方法。
請求項4
前記パス・ステップのうちの１つまたは複数でインデックスを指定するステップが、前記パス要素名に前記インデックスの述語を添付する、請求項１から３のいずれか一項に記載の方法。
請求項5
情報を取得するステップが、前記スキーマ（１０３）内での属性の最大出現に注目するステップと、これが存在しないかまたは１である場合、１の前記述語を前記パス要素名に添付するステップとを含む、前記請求項のいずれか一項に記載の方法。
請求項6
前記スキーマ（１０３）が、前記データ構造（１０１）の要素（１１０）をそのルートまで追跡するための情報を含む、前記請求項のいずれか一項に記載の方法。
請求項7
前記入力パス式（１０４）がＸＰａｔｈ式であり、前記データ構造（１０１）が関連付けられたスキーマ（１０３）を備えたドキュメント・オブジェクト・モデル構造である、前記請求項のいずれか一項に記載の方法。
請求項8
ランタイム時にデータ構造（１０１）内で１つまたは複数の要素（１１０）を見つけるために、データ構造（１０１）の照会のための入力パス式（１０４）を受信するための手段であって、前記入力パス式（１０４）は１つまたは複数のパス・ステップを含む、受信するための手段と、前記データ構造（１０１）のスキーマ（１０３）にアクセスし、前記１つまたは複数の要素（１１０）に関する情報を取得するための手段と、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数の前記パス・ステップにおけるインデックスを指定するように前記入力パス式（１０４）を修正するための手段と、前記データ構造（１０１）を照会（１１１）するためにランタイム時に使用するように修正された前記パス式を出力するための手段と、を備える、データ構造（１０１）のナビゲーションのためのシステム。
請求項9
前記入力パス式（１０４）が、ワイルドカード文字または下位軸のうちの１つまたは複数を含む、請求項８に記載のシステム。
請求項10
前記入力パス式（１０４）を修正するための手段が前記要素（１１０）の１つまたは複数の全パスを指定し、２つまたはそれ以上の全パスが合併演算子によって組み合わせられる、請求項８または９に記載のシステム。
請求項11
前記パス・ステップのうちの１つまたは複数でインデックスを指定することが、前記パス要素名に前記インデックスの述語を添付する、請求項８から１０のいずれか一項に記載のシステム。
請求項12
情報を取得するステップが、前記スキーマ（１０３）内での属性の最大出現に注目するための手段と、これが存在しないかまたは１である場合、１の前記述語を前記パス要素名に添付するための手段とを含む、請求項８から１１のいずれか一項に記載のシステム。
請求項13
前記スキーマ（１０３）が、前記データ構造（１０１）の要素（１１０）をそのルートまで追跡するための情報を含む、請求項８から１２のいずれか一項に記載のシステム。
請求項14
前記入力パス式（１０４）がＸＰａｔｈ式であり、前記データ構造（１０１）が関連付けられたスキーマ（１０３）を備えたドキュメント・オブジェクト・モデル構造である、請求項８から１３のいずれか一項に記載のシステム。
請求項15
前記システムが、ランタイム時に配置されることになる照会を構築するためのツールキット（１０５）である、請求項８から１４のいずれか一項に記載のシステム。
請求項16
前記スキーマ（１０３）へアクセスしないランタイム・エンジン（１０２）を含み、前記ランタイム・エンジン（１０２）が、データ構造（１０１）内で１つまたは複数の要素（１１０）を見つけるために前記修正されたパス式を使用する、請求項８から１５のいずれか一項に記載のシステム。
請求項17
前記ランタイム・エンジン（１０２）がメッセージ・ブローカであり、前記データ構造（１０１）がメッセージである、請求項１６に記載のシステム。
請求項18
ランタイム時にデータ構造（１０１）内で１つまたは複数の要素（１１０）を見つけるために、データ構造（１０１）の照会のための入力パス式（１０４）を受信するステップであって、前記入力パス式（１０４）は１つまたは複数のパス・ステップを含む、受信するステップと、前記データ構造（１０１）のスキーマ（１０３）にアクセスするステップ、および、前記１つまたは複数の要素（１１０）に関する情報を取得するステップと、パス・ステップ内で見つかった要素の出現数を制限するために、１つまたは複数の前記パス・ステップにおけるインデックスを指定するように前記入力パス式（１０４）を修正するステップと、ランタイム時に前記データ構造（１０１）を照会（１１１）するために前記修正されたパス式を使用するステップと、を実行するための、コンピュータ読み取り可能プログラム・コード手段を備える、コンピュータ読み取り可能ストレージ・メディア上に格納されたコンピュータ・プログラム。
請求項19
前記プログラムがコンピュータ上で実行された場合、請求項１から７のいずれか一項に記載の方法を実行するように適合されたプログラム・コード手段を備える、コンピュータ・プログラム。